package 栈和队列;

import java.util.Stack;

/**
 * @description:
 * @author: ywk 计算跨度
 * @date: 2020-06-28
 */
public class CalSpan {
    //暴力遍历
   static public int[] FindSpans(int[] arr) {
        int[] result = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            int span = 1;
            int j = i - 1;
            while (j >= 0 && arr[j] <= arr[j + 1]) {
                span++;
                j--;
            }
            result[i] = span;
        }
       printArr(result);
        return result;
    }

    static  int[] FindSpansWithStack(int[] arr) {
        int[] spans = new int[arr.length];
        Stack<Integer> stack = new Stack<>();
        int p = 0;
        for (int i = 0; i < arr.length; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
                stack.pop();
            }
            if (stack.isEmpty()) {
                p = -1;
            }else{
                p = stack.peek();
            }
            spans[i] = i - p;
            stack.push(i);
        }
        printArr(spans);

        return spans;
    }

    public static void printArr(int[] arr) {
        for (int i : arr) {
            System.out.println(i);
        }
    }
    public static void main(String[] args) {
        int[] arr = {6, 3, 4, 5, 2};
        FindSpans(arr);
        FindSpansWithStack(arr);
    }
}
